package online.longzipeng;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lzp
 * @Date:2023/10/13
 * @description: 随机链表的复制
 * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点
 */
public class Solution138 {

	/**
	 * 利用数组存引用的索引，克隆完毕后，直接遍历引用索引补全节点的random
	 */
	public static Node copyRandomList(Node head) {
		// 克隆第一场节点，并存储每一级的引用序列
		Node newNode = new Node(-1);
		Node pre = newNode;
		Node cur = head;

		List<Integer> refArr = new ArrayList<>();
		List<Node> newNodes = new ArrayList<>();
		int i = 0;
		while (cur != null) {
			// 记录当前节点引用的节点在节点中的索引，0表示null
			if (cur.random == null) {
				refArr.add(i++, -1);
			} else {
				// 二次遍历查值
				Node sCur = head;
				int j = 0;
				while (sCur != null) {
					if (cur.random == sCur) {
						refArr.add(i++, j);
						break;
					}
					sCur = sCur.next;
					j++;
				}
			}
			// 克隆一级节点
			pre.next = new Node(cur.val);
			newNodes.add(pre.next);
			pre = pre.next;
			cur = cur.next;
		}

		// 遍历补充二级节点的引用
		for (i = 0; i < newNodes.size(); i++) {
			Integer refIndex = refArr.get(i);
			if (refIndex != -1) {
				newNodes.get(i).random = newNodes.get(refIndex);
			}
		}

		return newNode.next;
	}

	/**
	 * hashMap存储原节点和新节点的映射，更快的取到random
	 */
	public static Node copyRandomList2(Node head) {
		if(head==null){
			return null;
		}
		Node tempNode = head;
		Map<Node, Node> map = new HashMap<>();
		while (tempNode != null) {
			map.put(tempNode, new Node(tempNode.val));
			tempNode = tempNode.next;
		}

		tempNode = head;
		while (tempNode != null) {
			map.get(tempNode).next = map.get(tempNode.next);
			map.get(tempNode).random = map.get(tempNode.random);
			tempNode = tempNode.next;
		}
		return map.get(head);
	}

	public static void main(String[] args) {
		Node node1 = new Node(7);
		Node node2 = new Node(13);
		Node node3 = new Node(11);
		Node node4 = new Node(10);
		Node node5 = new Node(1);

		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;

		node2.random = node1;
		node3.random = node5;
		node4.random = node3;
		node5.random = node1;

		Node nodeCp = copyRandomList(node1);

		while (nodeCp != null) {
			System.out.println(nodeCp);
			nodeCp = nodeCp.next;
		}
	}

}
